package done.normal_101_200;

import com.study.common.TreeNode;
import org.junit.Test;

import java.util.*;

import static com.study.util.LogUtil.info;

/**
 * 113. Path Sum II 路径总和 II
 * <p>
 * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例: 给定如下二叉树，以及目标和 sum = 22，
 * 5
 * / \
 * 4   8
 * /   / \
 * 11  13  4
 * /  \    / \
 * 7    2  5   1
 * <p>
 * 返回:[
 * [5,4,11,2],
 * [5,8,4,5]
 * ]
 * <p>
 * 2019-05-17 21:02
 **/
@SuppressWarnings("all")
public class PathSumII {

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        // 190517 first
        return null;
    }


    @Test
    public void test() {
        info("\n[[5, 4, 11, 2], [5, 8, 4, 5]] \n{}", pathSum(
                new TreeNode(5,
                        new TreeNode(4,
                                new TreeNode(11,
                                        7, 2)), new TreeNode(8,
                        13, new TreeNode(4,
                        5, 1))), 22));
    }
}





























/*
List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    // 回溯 3ms
    dfs(root, new ArrayList<>(), sum);
    return res;
}

private void dfs(TreeNode root, List<Integer> list, int sum) {
    if (root == null)
        return;

    if (root.left == null && root.right == null) {
        list.add(root.val);

        if (sum == root.val)
            res.add(new ArrayList(list));

        list.remove(list.size() - 1);
        return;
    }

    list.add(root.val);

    dfs(root.left, list, sum - root.val);

    dfs(root.right, list, sum - root.val);

    list.remove(list.size() - 1);
}
*/
